package leetcode.editor.cn.q1_300.q200;
//在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。 
//
// 
//
// 示例 1： 
// 
// 
//输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"]
//,["1","0","0","1","0"]]
//输出：4
// 
//
// 示例 2： 
// 
// 
//输入：matrix = [["0","1"],["1","0"]]
//输出：1
// 
//
// 示例 3： 
//
// 
//输入：matrix = [["0"]]
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// m == matrix.length 
// n == matrix[i].length 
// 1 <= m, n <= 300 
// matrix[i][j] 为 '0' 或 '1' 
// 
//
// 👍 1446 👎 0

/**
 * 思路:
 * 动态规划
 * 记录 [i,j] 为右下角的正方形的最大边长
 */
public class Q221_MaximalSquare {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maximalSquare(char[][] matrix) {
            int maxEdge = 0;
            int m = matrix.length;
            int n = matrix[0].length;

            // 记录以 [i,j] 为右下角的正方形的最大边长
            int[][] edges = new int[m][n];

            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (matrix[i][j] == '0') {
                        edges[i][j] = 0;
                    } else {
                        if (i == 0 || j == 0) {
                            edges[i][j] = 1;
                        } else {
//                            edges[i][j] = edges[i - 1][j - 1] + 1;
                            edges[i][j] = Math.min(edges[i - 1][j - 1], Math.min(edges[i][j - 1], edges[i - 1][j])) + 1;
                        }
                    }
                    maxEdge = Math.max(maxEdge, edges[i][j]);
                }
            }


            return maxEdge * maxEdge;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q221_MaximalSquare().new Solution();
        // TO TEST
        System.out.println(solution.maximalSquare(new char[][]{
                {'1', '0', '1', '0'},
                {'1', '0', '1', '1'},
                {'1', '0', '1', '1'},
                {'1', '1', '1', '1'}}));
        System.out.println(solution.maximalSquare(new char[][]{{'1', '0', '1', '0', '0'}, {'1', '0', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'1', '0', '0', '1', '0'}}));
        System.out.println(solution.maximalSquare(new char[][]{{'0', '1'}, {'1', '0'}}));
        System.out.println(solution.maximalSquare(new char[][]{{'0'}}));
        System.out.println(solution.maximalSquare(new char[][]{{'1'}}));
    }
}